package datatypes.kdTree;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Future;

import controller.Globals;
import datatypes.Vertex;

/**
 * KdTree is a container class for KdTreeElements. KdTree manages properties
 * common to all KdTreeElements within this tree and also serves as the front
 * end for operations on the tree.
 * 
 * @author nils
 * 
 */
public class KdTree implements Iterable<Vertex> {
	private static final long serialVersionUID = 1L;
	
	/** the geometric data this tree is built from */
	public Vertex[] geometry;
	/** The number of axes */
	protected int dimensions = 1;
	/** Keeps track of the depth of the tree */
	public int maxDepth = 0;
	/** The root element */
	protected KdTreeElement root;
	
	public KdTree(Vertex[] geometry, int dimension) {
		this.geometry = geometry;
		this.dimensions = dimension;
		// Actually build the tree and assign its root to the root ivar:
		this.root = new KdTreeElement(geometry, this);
	}

	/**
	 * Accessor to conveniently address KdTreeElements by specifying depth and
	 * index. Depth should be self-explanatory, index is the count of elements
	 * starting from zero and from the left. getElement(0,0) will return the
	 * root element, getElement(2,0) the leftmost and getElement(2,3) the
	 * rightmost element on level 2.
	 * 
	 * Returns null if there is no element at the specified location.
	 * 
	 * @param depth
	 * @param index
	 * @return KdTreeElement The Element or null if there is no element at the
	 *         location specified
	 */
	public KdTreeElement getElement(int depth, int index) {
		return root.getElement(depth, index);
	}
	
	/**
	 * Returns the depth of the tree.
	 * @return
	 */
	int getMaxDepth() {
		return this.maxDepth;
	}
	
	/**
	 * Returns the number of axes of the tree; that is, a 3d-tree has 3 axes.
	 * @return
	 */
	public int getDimensions() {
		return this.dimensions;
	}
	
	/**
	 * Get-accessor to the root KdTreeElement.
	 * @return
	 */
	public KdTreeElement getRoot() {
		return this.root;
	}
	
	/**
	 * Search the tree for the given query range.
	 * The search algorithm will issue the following Notifications via the default NotificationCenter
	 * for views too hook in and visualize the search:
	 * * Notification.willTraverseElement
	 * * Notification.didTraverseElement
	 * * Notification.didFindLeaf
	 * * Notification.doesNotIntersect
	 * * Notification.willReportAllLeaves
	 * Each Notification will contain the relevant KdTreeElement as its sender.
	 * @param queryRange
	 * @return
	 * @throws InterruptedException
	 * @throws ExecutionException
	 */
	public Future<List<KdTreeElement>> searchForElements(final Range queryRange) throws InterruptedException, ExecutionException {
		return searchForElements(root, queryRange);
	}
	
	public Future<List<KdTreeElement>> searchForElements(final KdTreeElement element, final Range queryRange) {
		
		ExecutorService executer = Globals.mainExecutor;
		Future<List<KdTreeElement>> future = executer.submit(new Callable<List<KdTreeElement>>() {
			public List<KdTreeElement> call() throws Exception {
				List<KdTreeElement> foundLeaves = new ArrayList<KdTreeElement>();
				search(element, queryRange, foundLeaves);
				System.out.println("Found " + foundLeaves.size() + " matching leaves.");
				return foundLeaves;
			}
		});
		return future;
	}
	
	
	/**
	 * Search the tree for the given query range.
	 * The search algorithm will issue the following Notifications via the default NotificationCenter
	 * for views too hook in and visualize the search:
	 * * Notification.willTraverseElement
	 * * Notification.didTraverseElement
	 * * Notification.didFindLeaf
	 * * Notification.doesNotIntersect
	 * * Notification.willReportAllLeaves
	 * Each Notification will contain the relevant KdTreeElement as its sender.
	 * @param queryRange
	 * @return
	 * @throws InterruptedException
	 * @throws ExecutionException
	 */
	public Future<List<Vertex>> search(final Range queryRange) throws InterruptedException, ExecutionException {
		return search(root, queryRange);
	}

	private Future<List<Vertex>> search(final KdTreeElement element, final Range queryRange) {
		
		ExecutorService executer = Globals.mainExecutor;
		Future<List<Vertex>> future = executer.submit(new Callable<List<Vertex>>() {
			public List<Vertex> call() throws Exception {
				List<KdTreeElement> foundLeaves = new ArrayList<KdTreeElement>();
				search(element, queryRange, foundLeaves);
				List<Vertex> vertices = new ArrayList<Vertex>();
				for (KdTreeElement leaf : foundLeaves) {
					vertices.add(leaf.median);
				}
				return vertices;
			}
		});
		return future;
	}
	
	/**
	 * See algorithm on page 103. Line numbers given as comments.
	 * @param element
	 * @param queryRange
	 * @param foundLeaves
	 * @return
	 */
	private List<KdTreeElement> search(KdTreeElement element, Range queryRange, List<KdTreeElement> foundLeaves) {
		if (element.isLeaf()) {								// 1.
			if (queryRange.contains(element.median)) {
				foundLeaves.add(element);						// 2.
			}
			return foundLeaves;
		}
		
		for (int i = 0; i < 2; i++) {
			KdTreeElement branch;
			if (i == 0) {
				branch = element.left;
			} else {
				branch = element.right;
			}
			
			if (branch != null) {
				if (queryRange.contains(branch.range)) {				// 3. / 7.
					List<KdTreeElement> reportedLeaves = getLeaves(branch);
					foundLeaves.addAll(reportedLeaves);				// 4. / 8.
				} else {
					if (queryRange.intersects(branch.range)) {		// 5. / 9.
						search(branch, queryRange, foundLeaves);			// 6. / 10.
					}
				}
			}
		}
		return foundLeaves;
	}
	
	protected void sleep(int milliseconds) {
		try {
			Thread.sleep(milliseconds);
		} catch (InterruptedException e1) {
			e1.printStackTrace();
		}
	}
	
	/**
	 * Collects all leaves of a subtree given by the parameter rootElement.
	 * @param rootElement
	 * @return A list of all leaves of the subtree.
	 */
	public List<KdTreeElement> getLeaves(KdTreeElement rootElement) {
		return dfsTree(rootElement, false, true);
	}
	
	/**
	 * Returns a list of KdTreeElements of the given subtree.
	 * See {@link #bfsTree()} or {@link #dfsTree()} to get a list of the whole tree.
	 * @param rootElement
	 * @param reportNodes If false, all nodes will be omitted.
	 * @param reportLeaves If false, all leaves will be omitted.
	 * @return
	 */
	public List<KdTreeElement> dfsTree(KdTreeElement rootElement, boolean reportNodes, boolean reportLeaves) {
		List<KdTreeElement> $ret = new ArrayList<KdTreeElement>();
		Stack<KdTreeElement> stack = new Stack<KdTreeElement>();
		KdTreeElement currentNode;
		
		stack.add(rootElement);
		while(!stack.isEmpty()) {
			currentNode = stack.pop();
			if (	(reportLeaves && currentNode.isLeaf())
				||	(reportNodes && !currentNode.isLeaf()) ) {
				$ret.add(currentNode);
			}
			if(!currentNode.isLeaf()) {
				stack.add(currentNode.right);
				stack.add(currentNode.left);
			}
		}
		return $ret;
	}
	
	
	/**
	 * Returns a nodelist of the tree in bfs-order
	 */
	public List<KdTreeElement> bfsTree() {
		List<KdTreeElement> $ret = new ArrayList<KdTreeElement>();
		Queue<KdTreeElement> queue = new LinkedList<KdTreeElement>();
		KdTreeElement currentNode;
		
		queue.add(root);
		while(!queue.isEmpty()) {
			currentNode = queue.poll();
			$ret.add(currentNode);
			if(!currentNode.isLeaf()) {
				queue.add(currentNode.left);
				queue.add(currentNode.right);
			}
		}
		return $ret;
	}
	
	public Iterable<Vertex> rangeIterator(Range range) {
		return new RangeIterator(range, this);
	}

	/**
	 * Returns a nodelist of the tree in dfs-order
	 */
	public List<KdTreeElement> dfsTree() {
		return dfsTree(root, true, true);
	}

	@Override
	public Iterator<Vertex> iterator() {
		return new ArrayIterator<Vertex>(geometry);
	}

	public int size() {
		return geometry.length;
	}

	public datatypes.Vertex get(int i) {
		return geometry[i];
	}

	public boolean isEmpty() {
		return geometry.length == 0;
	}

}
